home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 24 / CU Amiga Magazine's Super CD-ROM 24 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-07].iso / CUCD / Programming / SWI / source / src / pl-glob.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-08-07  |  11.6 KB  |  576 lines
  1. /*  $Id: pl-glob.c,v 1.23 1997/08/07 07:58:01 jan Exp $
  2.  
  3.     Copyright (c) 1990 Jan Wielemaker. All rights reserved.
  4.     See ../LICENCE to find out about your rights.
  5.     jan@swi.psy.uva.nl
  6.  
  7.     Purpose: File Name Expansion
  8. */
  9.  
  10. #if __TOS__
  11. #include <tos.h>
  12. #define HIDDEN    0x02
  13. #define SUBDIR 0x10
  14. #endif
  15.  
  16. #include "pl-incl.h"
  17. #include "pl-ctype.h"
  18.  
  19. #ifdef HAVE_UNISTD_H
  20. #include <unistd.h>
  21. #endif
  22.  
  23. #ifdef __WATCOMC__
  24. #include <direct.h>
  25. #else /*__WATCOMC__*/
  26. #if HAVE_DIRENT_H
  27. # include <dirent.h>
  28. #else
  29. # define dirent direct
  30. # if HAVE_SYS_NDIR_H
  31. #  include <sys/ndir.h>
  32. # endif
  33. # if HAVE_SYS_DIR_H
  34. #  include <sys/dir.h>
  35. # endif
  36. # if HAVE_NDIR_H
  37. #  include <ndir.h>
  38. # endif
  39. #endif
  40. #endif /*__WATCOMC__*/
  41.  
  42. #ifdef HAVE_SYS_STAT_H
  43. #include <sys/stat.h>
  44. #endif
  45. #ifdef HAVE_SYS_PARAM_H
  46. #include <sys/param.h>
  47. #endif
  48.  
  49. #ifndef IS_DIR_SEPARATOR
  50. #define IS_DIR_SEPARATOR(c)    ((c) == '/')
  51. #endif
  52.  
  53.  
  54. /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  55. Unix Wildcard Matching.  Recognised:
  56.  
  57.   ?        matches one arbitrary character
  58.   *        matches any number of any character
  59.   [xa-z]    matches x and a-z
  60.   {p1,p2}    matches pattern p1 or p2
  61.  
  62.   backslash (\) escapes a character.
  63.  
  64. First the pattern is compiled into an intermediate representation.  Next
  65. this intermediate representation is matched  against  the  target.   The
  66. non-ascii  characters  are  used  to  store  control  sequences  in  the
  67. intermediate representation:
  68.  
  69.   ANY        Match any character
  70.   STAR        Match (possibly empty) sequence
  71.   ALT <offset>    Match, if fails, continue at <pc> + offset
  72.   JMP <offset>    Jump <offset> instructions
  73.   ANYOF        Next 16 bytes are bitmap
  74. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  75.  
  76. #define MAXEXPAND    1024
  77. #define NextIndex(i)    ((i) < MAXEXPAND-1 ? (i)+1 : 0)
  78.  
  79. #define MAXCODE 1024
  80.  
  81. #define ANY    128
  82. #define STAR    129
  83. #define ALT    130
  84. #define JMP    131
  85. #define ANYOF    132
  86. #define EXIT    133
  87.  
  88. #define NOCURL    0
  89. #define CURL    1
  90.  
  91. typedef unsigned char matchcode;
  92.  
  93. struct bag
  94. { int     in;            /* in index */
  95.   int     out;            /* out index */
  96.   int     size;            /* number of entries */
  97.   bool     changed;        /* did bag change? */
  98.   bool     expanded;        /* Expanded bag? */
  99.   char    *bag[MAXEXPAND];    /* bag of paths */
  100. };
  101.  
  102. typedef struct
  103. { int        size;
  104.   matchcode    code[MAXCODE];
  105. } compiled_pattern;
  106.  
  107. forwards char    *compile_pattern(compiled_pattern *, char *, int);
  108. forwards bool    match_pattern(matchcode *, char *);
  109. forwards int    stringCompare(const void *, const void *);
  110. forwards bool    expand(char *, char **, int *);
  111. #ifdef O_EXPANDS_TESTS_EXISTS
  112. forwards bool    Exists(char *);
  113. #endif
  114. forwards char    *change_string(char *, char *);
  115. forwards bool    expandBag(struct bag *);
  116.  
  117. #define Output(c)    { if ( Out->size > MAXCODE-1 ) \
  118.               { warning("pattern too large"); \
  119.                 return (char *) NULL; \
  120.               } \
  121.               Out->code[Out->size++] = c; \
  122.             }
  123.  
  124. static inline void
  125. setMap(matchcode *map, int c)
  126. { if ( !trueFeature(FILE_CASE_FEATURE) )
  127.     c = makeLower(c);
  128.  
  129.   map[(c)/8] |= 1 << ((c) % 8);
  130. }
  131.  
  132.  
  133. static bool
  134. compilePattern(char *p, compiled_pattern *cbuf)
  135. { cbuf->size = 0;
  136.   if ( compile_pattern(cbuf, p, NOCURL) == (char *) NULL )
  137.     fail;
  138.  
  139.   succeed;
  140. }
  141.  
  142.  
  143. static char *
  144. compile_pattern(compiled_pattern *Out, char *p, int curl)
  145. { char c;
  146.  
  147.   for(;;)
  148.   { switch(c = *p++)
  149.     { case EOS:
  150.     break;
  151.       case '\\':
  152.     Output(*p == EOS ? '\\' : (*p & 0x7f));
  153.     if (*p == EOS )
  154.       break;
  155.     p++;
  156.     continue;
  157.       case '?':
  158.     Output(ANY);
  159.     continue;
  160.       case '*':
  161.     Output(STAR);
  162.     continue;
  163.       case '[':
  164.     { matchcode *map;
  165.       int n;
  166.  
  167.       Output(ANYOF);
  168.       map = &Out->code[Out->size];
  169.       Out->size += 16;
  170.       if ( Out->size >= MAXCODE )
  171.       { warning("Pattern too long");
  172.         return (char *) NULL;
  173.       }
  174.  
  175.       for( n=0; n < 16; n++)
  176.         map[n] = 0;
  177.  
  178.       for(;;)
  179.       { switch( c = *p++ )
  180.         { case '\\':
  181.         if ( *p == EOS )
  182.         { warning("Unmatched '['");
  183.           return (char *)NULL;
  184.         }
  185.         setMap(map, *p);
  186.         p++;
  187.         continue;
  188.           case ']':
  189.         break;
  190.           default:
  191.         if ( p[-1] != ']' && p[0] == '-' && p[1] != ']' )
  192.         { int chr;
  193.  
  194.           for ( chr=p[-1]; chr <= p[1]; chr++ )
  195.             setMap(map, chr);
  196.           p += 2;
  197.         } else
  198.           setMap(map, c);
  199.         continue;
  200.         }
  201.         break;
  202.       }
  203.  
  204.       continue;
  205.     }
  206.       case '{':
  207.     { int ai, aj = -1;
  208.  
  209.       for(;;)
  210.       { Output(ALT); ai = Out->size; Output(0);
  211.         if ( (p = compile_pattern(Out, p, CURL)) == (char *) NULL )
  212.           return (char *) NULL;
  213.         if ( aj > 0 )
  214.           Out->code[aj] = Out->size - aj;
  215.         if ( *p == ',' )
  216.         { Output(JMP); aj = Out->size; Output(0);
  217.           Out->code[ai] = Out->size - ai;
  218.           Output(ALT); ai = Out->size; Output(0);
  219.           p++;
  220.         } else if ( *p == '}' )
  221.         { p++;
  222.           break;
  223.         } else
  224.         { warning("Unmatched '{'");
  225.           return (char *) NULL;
  226.         }
  227.       }
  228.       
  229.       continue;
  230.     }
  231.       case '}':
  232.       case ',':
  233.     if ( curl == CURL )
  234.     { p--;
  235.       return p;
  236.     }
  237.     /*FALLTHROUGH*/
  238.       default:
  239.     c &= 0x7f;
  240.     c = makeLower(c);
  241.     Output(c);
  242.     continue;
  243.     }
  244.  
  245.     Output(EXIT);
  246.     return p;
  247.   }
  248. }
  249.  
  250.  
  251. static inline bool
  252. matchPattern(char *s, compiled_pattern *cbuf)
  253. { return match_pattern(cbuf->code, s);
  254. }
  255.  
  256.  
  257. static bool
  258. match_pattern(matchcode *p, char *str)
  259. { matchcode c;
  260.   matchcode *s = (matchcode *) str;
  261.  
  262.   for(;;)
  263.   { switch( c = *p++ )
  264.     { case EXIT:
  265.       return (*s == EOS ? TRUE : FALSE);
  266.       case ANY:                        /* ? */
  267.       if ( *s == EOS )
  268.         fail;
  269.       s++;
  270.       continue;
  271.       case ANYOF:                    /* [...] */
  272.         { matchcode c2 = *s;
  273.  
  274.       if ( !trueFeature(FILE_CASE_FEATURE) )
  275.         c2 = makeLower(c2);
  276.  
  277.       if ( p[c2 / 8] & (1 << (c2 % 8)) )
  278.       { p += 16;
  279.         s++;
  280.         continue;
  281.       }
  282.       fail;
  283.     }
  284.       case STAR:                    /* * */
  285.       do
  286.       { if ( match_pattern(p, (char *)s) )
  287.           succeed;
  288.       } while( *s++ );
  289.       fail;
  290.       case JMP:                        /* { ... } */
  291.       p += *p;
  292.       continue;
  293.       case ALT:
  294.       if ( match_pattern(p+1, (char *)s) )
  295.         succeed;
  296.       p += *p;
  297.       continue;      
  298.       default:                        /* character */
  299.       if ( c == *s ||
  300.            (!trueFeature(FILE_CASE_FEATURE) && c == makeLower(*s)) )
  301.       { s++;
  302.         continue;
  303.       }
  304.           fail;
  305.     }
  306.   }
  307. }
  308.  
  309.  
  310. word
  311. pl_wildcard_match(term_t pattern, term_t string)
  312. { char *p;
  313.   compiled_pattern buf;
  314.  
  315.   if ( PL_get_chars(pattern, &p, CVT_ALL) &&
  316.        compilePattern(p, &buf) )
  317.   { char *s;
  318.  
  319.     if ( PL_get_chars(string, &s, CVT_ALL) )
  320.       return matchPattern(s, &buf);
  321.   }
  322.     
  323.   return warning("wildcard_match/2: instantiation fault");
  324. }
  325.  
  326. /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  327. File Name Expansion.
  328. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  329.  
  330. word
  331. pl_expand_file_name(term_t f, term_t list)
  332. { char spec[MAXPATHLEN];
  333.   char *s;
  334.   char *vector[MAXEXPAND];
  335.   char **v;
  336.   int filled;
  337.   term_t l    = PL_copy_term_ref(list);
  338.   term_t head = PL_new_term_ref();
  339.  
  340.   if ( !PL_get_chars(f, &s, CVT_ALL) )
  341.     return warning("expand_file_name/2: instantiation fault");
  342.   if ( strlen(s) > MAXPATHLEN-1 )
  343.     return warning("expand_file_name/2: name too long");
  344.  
  345.   TRY( expandVars(s, spec) );
  346.   TRY( expand(spec, vector, &filled) );
  347.  
  348.   for( v = vector; filled > 0; filled--, v++ )
  349.   { if ( !PL_unify_list(l, head, l) ||
  350.      !PL_unify_atom_chars(head, *v) )
  351.       fail;
  352.   }
  353.  
  354.   return PL_unify_nil(l);
  355. }
  356.  
  357.  
  358. static int
  359. stringCompare(const void *a1, const void *a2)
  360. { if ( trueFeature(FILE_CASE_FEATURE) )
  361.     return strcmp(*((char **)a1), *((char **)a2));
  362.   else
  363.     return stricmp(*((char **)a1), *((char **)a2));
  364. }
  365.  
  366. static bool
  367. expand(char *f, char **argv, int *argc)
  368. { struct bag b;
  369.  
  370.   b.changed = b.expanded = FALSE;
  371.   b.out = 0;            /* put the first entry in the bag */
  372.   b.in = b.size = 1;
  373.   b.bag[0] = store_string(f);
  374. #if tos || defined(__MSDOS__)    /* case insensitive: do all lower case */
  375.   strlwr(b.bag[0]);
  376. #endif
  377. /* Note for OS2: HPFS is case insensitive but case preserving. */
  378.  
  379.   do                /* expand till nothing to expand */
  380.   { b.changed = FALSE;  
  381.     TRY( expandBag(&b) );
  382.   } while( b.changed );
  383.  
  384.   { char **r = argv;
  385.     char plp[MAXPATHLEN];
  386.  
  387.     *argc = b.size;
  388.     for( ; b.out != b.in; b.out = NextIndex(b.out) )
  389.       *r++ = change_string(b.bag[b.out], PrologPath(b.bag[b.out], plp));
  390.     *r = (char *) NULL;
  391.     qsort(argv, b.size, sizeof(char *), stringCompare);
  392.  
  393.     succeed;
  394.   }
  395. }
  396.  
  397. #ifdef O_EXPANDS_TESTS_EXISTS
  398. #if defined(HAVE_STAT) || defined(__unix__)
  399. static bool
  400. Exists(const char *path)
  401. { char tmp[MAXPATHLEN];
  402.   struct stat buf;
  403.  
  404.   if ( stat(OsPath(path, tmp), &buf) == -1 )
  405.     fail;
  406.  
  407.   succeed;
  408. }
  409. #endif
  410.  
  411. #if tos
  412. static bool
  413. Exists(const path)
  414. char *path;
  415. { struct ffblk buf;
  416.   char tmp[MAXPATHLEN];
  417.  
  418.   DEBUG(2, Sdprintf("Checking existence of %s ... ", path));
  419.   if ( findfirst(OsPath(path, tmp), &buf, SUBDIR|HIDDEN) == 0 )
  420.   { DEBUG(2, Sdprintf("yes\n"));
  421.     succeed;
  422.   }
  423.   DEBUG(2, Sdprintf("no\n"));
  424.  
  425.   fail;
  426. }
  427. #endif
  428. #endif /*O_EXPANDS_TESTS_EXISTS*/
  429.  
  430. static char *
  431. change_string(char *old, char *new)
  432. { return store_string(new);
  433. }
  434.  
  435. static bool
  436. expandBag(struct bag *b)
  437. { int high = b->in;
  438.  
  439.   for( ; b->out != high; b->out = NextIndex(b->out) )
  440.   { char *head = b->bag[b->out];
  441.     char *tail;
  442.     char *s = head;
  443.     compiled_pattern cbuf;
  444.     
  445.     for(;;)
  446.     { int c;
  447.  
  448.       switch( (c = *s++) )
  449.       { case EOS:                /* no special characters */
  450. #ifdef O_EXPANDS_TESTS_EXISTS
  451.       if ( b->expanded == FALSE || Exists(b->bag[b->out]) )
  452.       { b->bag[b->in] = b->bag[b->out];
  453.         b->in = NextIndex(b->in);
  454.       } else
  455.       { b->size--;
  456.       }
  457. #else
  458.       b->bag[b->in] = b->bag[b->out];
  459.       b->in = NextIndex(b->in);
  460. #endif
  461.       goto next_bag;
  462.     case '[':                /* meta characters: expand */
  463.     case '{':
  464.     case '?':
  465.     case '*':
  466.       break;
  467.     default:
  468.       if ( IS_DIR_SEPARATOR(c) )
  469.         head = s;
  470.       continue;
  471.       }
  472.       break;
  473.     }
  474.  
  475.     b->expanded = b->changed = TRUE;
  476.     b->size--;
  477.     for( tail=s; *tail && !IS_DIR_SEPARATOR(*tail); tail++ )
  478.       ;
  479.  
  480. /*  By now, head points to the start of the path holding meta characters,
  481.     while tail points to the tail:
  482.  
  483.     ..../meta*path/....
  484.      ^        ^
  485.        head     tail
  486. */
  487.  
  488.     { char prefix[MAXPATHLEN];
  489.       char expanded[MAXPATHLEN];
  490.       char *path;
  491.       char *s, *q;
  492.       int dot;
  493.  
  494.       for( q=prefix, s=b->bag[b->out]; s < head; )
  495.     *q++ = *s++;
  496.       *q = EOS;
  497.       path = (prefix[0] == EOS ? "." : prefix);
  498.  
  499.       for( q=expanded, s=head; s < tail; )
  500.         *q++ = *s++;
  501.       *q = EOS;
  502.  
  503.       if ( !compilePattern(expanded, &cbuf) )        /* syntax error */
  504.         fail;
  505.       dot = (expanded[0] == '.');            /* do dots as well */
  506.  
  507. #ifdef HAVE_OPENDIR
  508.       { DIR *d;
  509.     char tmp[MAXPATHLEN];
  510.     struct dirent *e;
  511.  
  512.     d = opendir(OsPath(path, tmp));
  513.  
  514.     if ( d != NULL )
  515.     { for(e=readdir(d); e; e = readdir(d))
  516.       {
  517. #ifdef __MSDOS__
  518.         strlwr(e->d_name);
  519. #endif
  520.         if ( (dot || e->d_name[0] != '.') &&
  521.          matchPattern(e->d_name, &cbuf) )
  522.         { strcpy(expanded, prefix);
  523.           strcat(expanded, e->d_name);
  524.           strcat(expanded, tail);
  525.  
  526.           b->bag[b->in] = change_string(b->bag[b->out], expanded);
  527.           b->in = NextIndex(b->in);
  528.           b->size++;
  529.           if ( b->in == b->out )
  530.         return warning("Too many matches");
  531.         }
  532.       }
  533.       closedir(d);
  534.     }
  535.       }
  536. #endif /*HAVE_OPENDIR*/
  537.  
  538. #if tos
  539.       { char dpat[MAXPATHLEN];
  540.     struct ffblk buf;
  541.     int r;
  542.     char tmp[MAXPATHLEN];
  543.  
  544.     strcpy(dpat, path);
  545.     strcat(dpat, "\\*.*");
  546.  
  547.     DEBUG(2, Sdprintf("match path = %s\n", dpat));
  548.     for( r=findfirst(OsPath(dpat, tmp), &buf, SUBDIR|HIDDEN);
  549.          r == 0;
  550.          r=findnext(&buf) )
  551.     { char *name = buf.ff_name;
  552.       strlwr(name);        /* match at lower case */
  553.  
  554.       DEBUG(2, Sdprintf("found %s\n", name));
  555.       if ( (dot || name[0] != '.') && matchPattern(name, &cbuf) )
  556.       { strcpy(expanded, prefix);
  557.         strcat(expanded, name);
  558.         strcat(expanded, tail);
  559.  
  560.         DEBUG(2, Sdprintf("%s matches pattern\n", name));
  561.         b->bag[b->in] = change_string(b->bag[b->out], expanded);
  562.         b->in = NextIndex(b->in);
  563.         b->size++;
  564.         if ( b->in == b->out )
  565.           return warning("Too many matches");
  566.       }
  567.     }
  568.       }
  569. #endif /* tos */
  570.     }
  571.   next_bag:;
  572.   }
  573.  
  574.   succeed;
  575. }
  576.